package com.leetcode.algorithm.y22.m08.w2;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 39. 组合总和
 * 
 * https://leetcode.cn/problems/combination-sum/
 * 
 * @author jie.deng
 *
 */
class Question0039Solution01 {

	public List<List<Integer>> combinationSum(int[] candidates, int target) {
		List<List<Integer>> result = new ArrayList<>();
		Deque<Integer> path = new ArrayDeque<>();
		backtracking(candidates, target, result, 0, 0, path);
		return result;
	}

	private void backtracking(int[] candidates, int target, List<List<Integer>> result, int startIdx, int curSum,
			Deque<Integer> path) {
		// 递归终止条件
		if (curSum == target) {
			result.add(new ArrayList<>(path));
		}
		if (curSum > target) {
			return;
		}

		// 选择
		for (int i = startIdx; i < candidates.length; i++) {
			// 当前选择
			curSum += candidates[i];
			path.offerLast(candidates[i]);
			backtracking(candidates, target, result, i, curSum, path);

			// 回溯
			curSum -= candidates[i];
			path.pollLast();
		}
	}

}